import org.w3c.dom.ls.LSException;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution1 {
    List<List<Integer>> lists = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    int target;
    int count = 0;
    public List<List<Integer>> combinationSum(int[] candidates, int _target) {
        target = _target;
        Arrays.sort(candidates);
        dfs(candidates);
        return lists;
    }
    public void dfs(int[] candidates) {
        if(count > target) return;
        if(count == target) {
            lists.add(new ArrayList<>(list));
            return;
        }

        for(int i =0 ; i<candidates.length; i++) {
            if(candidates[i] > list.get(list.size()-1)) {
                list.add(candidates[i]);
                count += candidates[i];
                dfs(candidates);
                list.remove(list.size()-1);
                count -= candidates[i];
            }
        }
    }
}


class Solution2 {
    List<List<Integer>> lists = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    int target;
    int count = 0;
    public List<List<Integer>> combinationSum(int[] candidates, int _target) {
        target = _target;
        Arrays.sort(candidates);
        dfs(candidates,0);
        return lists;
    }
    public void dfs(int[] candidates,int start) {
        if(count > target) return;
        if(count == target) {
            lists.add(new ArrayList<>(list));
            return;
        }

        for(int i =start ; i<candidates.length; i++) {
            list.add(candidates[i]);
            count += candidates[i];
            dfs(candidates,start+1);
            list.remove(list.size()-1);
            count -= candidates[i];
        }
    }
}

class Solution3 {
    List<List<Integer>> lists = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    int target;
    int count = 0;
    boolean[] st;
    public List<List<Integer>> combinationSum2(int[] candidates, int _target) {
        target = _target;
        st = new boolean[candidates.length];
        Arrays.sort(candidates);
        dfs(candidates,0);
        return lists;
    }
    public void dfs(int[] candidates, int u) {
        if(u >= candidates.length || count > target) return;
        if(count == target) {
            lists.add(new ArrayList<>(list));
            return;
        }

        for(int i = u; i<candidates.length; i++) {
            if(!st[i] && candidates[i] > list.get(list.size()-1)) {
                list.add(candidates[i]);
                count += candidates[i];
                st[i] = true;
                dfs(candidates,i);
                list.remove(list.size()-1);
                count -= candidates[i];
                st[i] = false;
            }
        }
    }
}

class Solution {
    public int getSum(int a, int b) {
        while(b!=0) {
            int x = a^b;
            int y = a&b;
            a = x;
            b = y<<1;
        }
        return a;
    }
}

public class Test {
    public static void main(String[] args) {
        int[] nums = {2,5,2,1,2};
        List<List<Integer>> ret = new Solution3().combinationSum2(nums,5);
    }
}
